<?php

/**
 * Class Binarizer
 *
 * @created      17.01.2021
 *
 * @author       ZXing Authors
 * @author       Smiley <smiley@chillerlan.net>
 * @copyright    2021 Smiley
 * @license      Apache-2.0
 */
declare(strict_types=1);

namespace zxf\QrCode\Decoder;

use zxf\QrCode\Common\LuminanceSourceInterface;
use zxf\QrCode\Data\QRMatrix;

use function array_fill;
use function count;
use function intdiv;
use function max;

/**
 * This class implements a local thresholding algorithm, which while slower than the
 * GlobalHistogramBinarizer, is fairly efficient for what it does. It is designed for
 * high frequency images of barcodes with black data on white backgrounds. For this application,
 * it does a much better job than a global blackpoint with severe shadows and gradients.
 * However, it tends to produce artifacts on lower frequency images and is therefore not
 * a good general purpose binarizer for uses outside ZXing.
 *
 * This class extends GlobalHistogramBinarizer, using the older histogram approach for 1D readers,
 * and the newer local approach for 2D readers. 1D decoding using a per-row histogram is already
 * inherently local, and only fails for horizontal gradients. We can revisit that problem later,
 * but for now it was not a win to use local blocks for 1D.
 *
 * This Binarizer is the default for the unit tests and the recommended class for library users.
 *
 * @author dswitkin@google.com (Daniel Switkin)
 */
final class Binarizer
{
    // This class uses 5x5 blocks to compute local luminance, where each block is 8x8 pixels.
    // So this is the smallest dimension in each axis we can accept.
    private const BLOCK_SIZE_POWER = 3;

    private const BLOCK_SIZE = 8;  // ...0100...00

    private const BLOCK_SIZE_MASK = 7;  // ...0011...11

    private const MINIMUM_DIMENSION = 40;

    private const MIN_DYNAMIC_RANGE = 24;

    //	private const LUMINANCE_BITS    = 5;
    private const LUMINANCE_SHIFT = 3;

    private const LUMINANCE_BUCKETS = 32;

    private LuminanceSourceInterface $source;

    /** @var int[] */
    private array $luminances;

    public function __construct(LuminanceSourceInterface $source)
    {
        $this->source = $source;
        $this->luminances = $this->source->getLuminances();
    }

    /**
     * @param  int[]  $buckets
     *
     * @throws \zxf\QrCode\Decoder\QRCodeDecoderException
     */
    private function estimateBlackPoint(array $buckets): int
    {
        // Find the tallest peak in the histogram.
        $numBuckets = count($buckets);
        $maxBucketCount = 0;
        $firstPeak = 0;
        $firstPeakSize = 0;

        for ($x = 0; $x < $numBuckets; $x++) {

            if ($buckets[$x] > $firstPeakSize) {
                $firstPeak = $x;
                $firstPeakSize = $buckets[$x];
            }

            if ($buckets[$x] > $maxBucketCount) {
                $maxBucketCount = $buckets[$x];
            }
        }

        // Find the second-tallest peak which is somewhat far from the tallest peak.
        $secondPeak = 0;
        $secondPeakScore = 0;

        for ($x = 0; $x < $numBuckets; $x++) {
            $distanceToBiggest = ($x - $firstPeak);
            // Encourage more distant second peaks by multiplying by square of distance.
            $score = ($buckets[$x] * $distanceToBiggest * $distanceToBiggest);

            if ($score > $secondPeakScore) {
                $secondPeak = $x;
                $secondPeakScore = $score;
            }
        }

        // Make sure firstPeak corresponds to the black peak.
        if ($firstPeak > $secondPeak) {
            $temp = $firstPeak;
            $firstPeak = $secondPeak;
            $secondPeak = $temp;
        }

        // If there is too little contrast in the image to pick a meaningful black point, throw rather
        // than waste time trying to decode the image, and risk false positives.
        if (($secondPeak - $firstPeak) <= ($numBuckets / 16)) {
            throw new QRCodeDecoderException('no meaningful dark point found'); // @codeCoverageIgnore
        }

        // Find a valley between them that is low and closer to the white peak.
        $bestValley = ($secondPeak - 1);
        $bestValleyScore = -1;

        for ($x = ($secondPeak - 1); $x > $firstPeak; $x--) {
            $fromFirst = ($x - $firstPeak);
            $score = ($fromFirst * $fromFirst * ($secondPeak - $x) * ($maxBucketCount - $buckets[$x]));

            if ($score > $bestValleyScore) {
                $bestValley = $x;
                $bestValleyScore = $score;
            }
        }

        return $bestValley << self::LUMINANCE_SHIFT;
    }

    /**
     * Calculates the final BitMatrix once for all requests. This could be called once from the
     * constructor instead, but there are some advantages to doing it lazily, such as making
     * profiling easier, and not doing heavy lifting when callers don't expect it.
     *
     * Converts a 2D array of luminance data to 1 bit data. As above, assume this method is expensive
     * and do not call it repeatedly. This method is intended for decoding 2D barcodes and may or
     * may not apply sharpening. Therefore, a row from this matrix may not be identical to one
     * fetched using getBlackRow(), so don't mix and match between them.
     *
     * @return \zxf\QrCode\Decoder\BitMatrix The 2D array of bits for the image (true means black).
     */
    public function getBlackMatrix(): BitMatrix
    {
        $width = $this->source->getWidth();
        $height = $this->source->getHeight();

        if ($width >= self::MINIMUM_DIMENSION && $height >= self::MINIMUM_DIMENSION) {
            $subWidth = ($width >> self::BLOCK_SIZE_POWER);

            if (($width & self::BLOCK_SIZE_MASK) !== 0) {
                $subWidth++;
            }

            $subHeight = ($height >> self::BLOCK_SIZE_POWER);

            if (($height & self::BLOCK_SIZE_MASK) !== 0) {
                $subHeight++;
            }

            return $this->calculateThresholdForBlock($subWidth, $subHeight, $width, $height);
        }

        // If the image is too small, fall back to the global histogram approach.
        return $this->getHistogramBlackMatrix($width, $height);
    }

    private function getHistogramBlackMatrix(int $width, int $height): BitMatrix
    {

        // Quickly calculates the histogram by sampling four rows from the image. This proved to be
        // more robust on the blackbox tests than sampling a diagonal as we used to do.
        $buckets = array_fill(0, self::LUMINANCE_BUCKETS, 0);
        $right = intdiv(($width * 4), 5);
        $x = intdiv($width, 5);

        for ($y = 1; $y < 5; $y++) {
            $row = intdiv(($height * $y), 5);
            $localLuminances = $this->source->getRow($row);

            for (; $x < $right; $x++) {
                $pixel = ($localLuminances[$x] & 0xFF);
                $buckets[($pixel >> self::LUMINANCE_SHIFT)]++;
            }
        }

        $blackPoint = $this->estimateBlackPoint($buckets);

        // We delay reading the entire image luminance until the black point estimation succeeds.
        // Although we end up reading four rows twice, it is consistent with our motto of
        // "fail quickly" which is necessary for continuous scanning.
        $matrix = new BitMatrix(max($width, $height));

        for ($y = 0; $y < $height; $y++) {
            $offset = ($y * $width);

            for ($x = 0; $x < $width; $x++) {
                $matrix->set($x, $y, (($this->luminances[($offset + $x)] & 0xFF) < $blackPoint), QRMatrix::M_DATA);
            }
        }

        return $matrix;
    }

    /**
     * Calculates a single black point for each block of pixels and saves it away.
     * See the following thread for a discussion of this algorithm:
     *
     * @see http://groups.google.com/group/zxing/browse_thread/thread/d06efa2c35a7ddc0
     *
     * @return float[][]
     */
    private function calculateBlackPoints(int $subWidth, int $subHeight, int $width, int $height): array
    {
        $blackPoints = array_fill(0, $subHeight, array_fill(0, $subWidth, 0));

        for ($y = 0; $y < $subHeight; $y++) {
            $yoffset = ($y << self::BLOCK_SIZE_POWER);
            $maxYOffset = ($height - self::BLOCK_SIZE);

            if ($yoffset > $maxYOffset) {
                $yoffset = $maxYOffset;
            }

            for ($x = 0; $x < $subWidth; $x++) {
                $xoffset = ($x << self::BLOCK_SIZE_POWER);
                $maxXOffset = ($width - self::BLOCK_SIZE);

                if ($xoffset > $maxXOffset) {
                    $xoffset = $maxXOffset;
                }

                $sum = 0;
                $min = 255;
                $max = 0;

                for ($yy = 0, $offset = ($yoffset * $width + $xoffset); $yy < self::BLOCK_SIZE; $yy++, $offset += $width) {

                    for ($xx = 0; $xx < self::BLOCK_SIZE; $xx++) {
                        $pixel = ((int) ($this->luminances[(int) ($offset + $xx)]) & 0xFF);
                        $sum += $pixel;
                        // still looking for good contrast
                        if ($pixel < $min) {
                            $min = $pixel;
                        }

                        if ($pixel > $max) {
                            $max = $pixel;
                        }
                    }

                    // short-circuit min/max tests once dynamic range is met
                    if (($max - $min) > self::MIN_DYNAMIC_RANGE) {
                        // finish the rest of the rows quickly
                        for ($yy++, $offset += $width; $yy < self::BLOCK_SIZE; $yy++, $offset += $width) {
                            for ($xx = 0; $xx < self::BLOCK_SIZE; $xx++) {
                                $sum += ((int) ($this->luminances[(int) ($offset + $xx)]) & 0xFF);
                            }
                        }
                    }
                }

                // The default estimate is the average of the values in the block.
                $average = ($sum >> (self::BLOCK_SIZE_POWER * 2));

                if (($max - $min) <= self::MIN_DYNAMIC_RANGE) {
                    // If variation within the block is low, assume this is a block with only light or only
                    // dark pixels. In that case we do not want to use the average, as it would divide this
                    // low contrast area into black and white pixels, essentially creating data out of noise.
                    //
                    // The default assumption is that the block is light/background. Since no estimate for
                    // the level of dark pixels exists locally, use half the min for the block.
                    $average = ($min / 2);

                    if ($y > 0 && $x > 0) {
                        // Correct the "white background" assumption for blocks that have neighbors by comparing
                        // the pixels in this block to the previously calculated black points. This is based on
                        // the fact that dark barcode symbology is always surrounded by some amount of light
                        // background for which reasonable black point estimates were made. The bp estimated at
                        // the boundaries is used for the interior.

                        // The (min < bp) is arbitrary but works better than other heuristics that were tried.
                        $averageNeighborBlackPoint = (
                            ($blackPoints[($y - 1)][$x] + (2 * $blackPoints[$y][($x - 1)]) + $blackPoints[($y - 1)][($x - 1)]) / 4
                        );

                        if ($min < $averageNeighborBlackPoint) {
                            $average = $averageNeighborBlackPoint;
                        }
                    }
                }

                $blackPoints[$y][$x] = $average;
            }
        }

        return $blackPoints;
    }

    /**
     * For each block in the image, calculate the average black point using a 5x5 grid
     * of the surrounding blocks. Also handles the corner cases (fractional blocks are computed based
     * on the last pixels in the row/column which are also used in the previous block).
     */
    private function calculateThresholdForBlock(int $subWidth, int $subHeight, int $width, int $height): BitMatrix
    {
        $matrix = new BitMatrix(max($width, $height));
        $blackPoints = $this->calculateBlackPoints($subWidth, $subHeight, $width, $height);

        for ($y = 0; $y < $subHeight; $y++) {
            $yoffset = ($y << self::BLOCK_SIZE_POWER);
            $maxYOffset = ($height - self::BLOCK_SIZE);

            if ($yoffset > $maxYOffset) {
                $yoffset = $maxYOffset;
            }

            for ($x = 0; $x < $subWidth; $x++) {
                $xoffset = ($x << self::BLOCK_SIZE_POWER);
                $maxXOffset = ($width - self::BLOCK_SIZE);

                if ($xoffset > $maxXOffset) {
                    $xoffset = $maxXOffset;
                }

                $left = $this->cap($x, 2, ($subWidth - 3));
                $top = $this->cap($y, 2, ($subHeight - 3));
                $sum = 0;

                for ($z = -2; $z <= 2; $z++) {
                    $br = $blackPoints[($top + $z)];
                    $sum += ($br[($left - 2)] + $br[($left - 1)] + $br[$left] + $br[($left + 1)] + $br[($left + 2)]);
                }

                $average = (int) ($sum / 25);

                // Applies a single threshold to a block of pixels.
                for ($j = 0, $o = ($yoffset * $width + $xoffset); $j < self::BLOCK_SIZE; $j++, $o += $width) {
                    for ($i = 0; $i < self::BLOCK_SIZE; $i++) {
                        // Comparison needs to be <= so that black == 0 pixels are black even if the threshold is 0.
                        $v = (((int) ($this->luminances[($o + $i)]) & 0xFF) <= $average);

                        $matrix->set(($xoffset + $i), ($yoffset + $j), $v, QRMatrix::M_DATA);
                    }
                }
            }
        }

        return $matrix;
    }

    /**
     * @noinspection PhpSameParameterValueInspection
     */
    private function cap(int $value, int $min, int $max): int
    {

        if ($value < $min) {
            return $min;
        }

        if ($value > $max) {
            return $max;
        }

        return $value;
    }
}
